package top.fengleifeng.question;

import top.fengleifeng.util.Constants;

import java.util.LinkedList;
import java.util.List;

/**
 * @program: leetcode-test
 * @description:
 * @author: fengleifeng
 * @create: 2020-10-19 17:55
 **/
public class Num386字典序排数 {
    class Solution {
        public List<Integer> lexicalOrder(int n) {
            List<Integer> list = new LinkedList<>();
            dfs(n, 0, 1, list);
            return list;
        }

        private void dfs(int maxValue, int num, int start, List<Integer> list) {
            if (num > maxValue) {
                return;
            }
            if (num > 0) {
                list.add(num);
            }
            for (int i = start > 0 ? 1 : 0; i < 10; i++) {
                dfs(maxValue, num * 10 + i, i, list);
            }
        }

        public List<Integer> lexicalOrder2(int n) {
            List<Integer> list = new LinkedList<>();
            for (int i = 1; i < 10; i++) {
                if (i <= n) {
                    list.add(i);
                    test(list, n, i);
                } else {
                    break;
                }
            }
            return list;
        }

        // i 代表了第i+1位数
        private void test(List<Integer> list, int n, int startNum) {
            startNum *= 10;
            for (int i = 0; i < 10; i++, startNum++) {
                if (startNum <= n) {
                    list.add(startNum);
                    test(list, n, startNum);
                } else {
                    return;
                }
            }
        }
    }

    public static void main(String[] args) {
        List<Integer> list = new Num386字典序排数().new Solution().lexicalOrder(11);
        Constants.pringLinkedList(list);
    }
}
